package demo;

import com.sun.source.tree.Tree;

import java.time.temporal.Temporal;
import java.util.ArrayList;
import java.util.List;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //合并两个有序链表
    static public ListNode ret = new ListNode(0,null);
    public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        dfs1(list1,list2);
        ListNode pcur = ret;
        return pcur.next;
    }

    private ListNode dfs1(ListNode l1, ListNode l2){
        if(l1 == null){
            return l2;
        }else if(l2 == null){
            return l1;
        }else if(l1 == null && l2 == null){
            return null;
        }

        if(l1.val<l2.val){
            ret.next = dfs1(l1.next,l2);
            //dfs(l1.next,l2);
        }else {
            ret.next = dfs1(l1,l2.next);
            //dfs(l1,l2.next);
        }
        return ret;
    }


    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        if(list1.val<=list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else {
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
    }

    //
    public boolean evaluateTree(TreeNode root) {
        return dfs2(root);
    }

    private boolean dfs2(TreeNode root){
        if(root.val == 1) return true;
        if(root.val == 0) return false;

        if(root.val == 3){
            return dfs2(root.left) && dfs2(root.right);
        }else {
            return dfs2(root.left) || dfs2(root.right);
        }
    }

    //求根节点到叶节点数字之和
    public int sumNumbers(TreeNode root) {
        return dfs3(root.left,root.val) + dfs3(root.right, root.val);
    }

    private int dfs3(TreeNode root, int presum){
        if(root.left == null && root.right == null){
            return presum*10+root.val;
        }
        return dfs3(root.left,presum*10+root.val)
                + dfs3(root.right,presum*10+root.val);
    }

    //二叉树剪枝
    public TreeNode pruneTree(TreeNode root) {
        dfs4(root);
        return root;
    }

    private TreeNode dfs4(TreeNode root){
        if(root == null){
            return null;
        }
        root.left = dfs4(root.left);
        root.right = dfs4(root.right);
        if(root.left == null && root.right == null && root.val == 0){
            return null;
        }
        return root;
    }


    //验证二叉搜索树
    public long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        boolean left = isValidBST(root.left);
        if(left == false) return false;
        boolean pcur = false;
        if(root.val>prev) {
            pcur = true;
            prev = root.val;
        }
        if(pcur == false) return false;

        boolean right = isValidBST(root.right);

        return right && pcur && left;
    }

//    private boolean dfs(TreeNode root){
//
//        if(dfs(root.left) == true){
//            if(root.val>prev){
//                return true;
//            }
//            if(dfs(root.right) == true){
//                return true;
//            }
//        }else {
//            return false;
//        }
//    }

    //二叉搜索树中第 K 小的元素
    public int count = 0;
    public int retkthSmallest = 0;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        dfs5(root);
        return retkthSmallest;
    }

    private void dfs5(TreeNode root){
        if(root == null) return ;
        if(count == 0){
            return;
        }
        dfs5(root.left);
        count--;
        if(count == 0) retkthSmallest = root.val;
        dfs5(root.right);
    }

    //二叉树的所有路径
    List<String> retbinary = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        dfs6(root,new StringBuffer());
        return retbinary;
    }

    private void dfs6(TreeNode root , StringBuffer path_){
        if(root == null) return ;
        StringBuffer path = new StringBuffer(path_);
        path.append(Integer.toString(root.val));
        if(root.left == null && root.right == null){
            retbinary.add(path.toString());
            return ;
        }else {
            path.append("->");
        }
        dfs6(root.left,path);
        dfs6(root.right,path);
    }

    //全排列
    static List<List<Integer>> retPermute ;
    static List<Integer> path;
    static boolean[] check ;
    public static List<List<Integer>> permute(int[] nums) {
        retPermute = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length];
        dfs(nums);
        return retPermute;
    }

    private static void dfs(int[] nums){
        if(path.size() == nums.length){
            retPermute.add(path);
            return ;
        }

        for (int i = 0; i < nums.length; i++) {
            if(check[i] == false){
                path.add(nums[i]);
                check[i] = true;
                dfs(nums);
                path.remove(path.size()-1);
                check[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        ret.add(list);
        list.remove(0);
        list.remove(0);
        //list.remove(3);
        ret.add(list);
        System.out.println(ret.toString());
//        int[] nums = {1,2,3};
//        permute(nums);
    }
}












